﻿namespace Gamelight.Graphics
{
	internal class PolygonDrawer
	{
		// The keys of this array are x-coordinates
		// the inner arrays are a lists of y-values of where the line segments
		// that cross that x coordinate.
		// These values are sorted. 
		// The exception are the first two elements in the inner array.
		// The first element is the number of segments in the list (should be 0 when empty
		// The second element is the actual capacity of the array (should be 2 when empty)
		private int[][] segment_range = new int[0][];

		private int segment_range_capacity = 0;
		private Point[] pointList = new Point[50];

		public void DrawPolygon(int[,] pixels, int[] column_affected, int[] y_min_affected, int[] y_max_affected, int counter, Point[][] points)
		{
			int xMin = 0;
			int yMin = 0;
			int xMax = 0;
			int yMax = 0;
			bool xyMinMaxInitialized = false;
			Point[] pointList;
			Point p;
			int i, j, x, y;
			for (i = 0; i < points.Length; ++i)
			{
				pointList = points[i];
				if (pointList.Length >= 3)
				{
					if (!xyMinMaxInitialized)
					{
						xyMinMaxInitialized = true;
						xMin = pointList[0].X;
						xMax = xMin;
						yMin = pointList[0].Y;
						yMax = yMin;
					}

					for (j = 0; j < pointList.Length; ++j)
					{
						p = pointList[j];
						x = p.X;
						y = p.Y;
						xMin = x < xMin ? x : xMin;
						xMax = x > xMax ? x : xMax;
						yMin = y < yMin ? y : yMin;
						yMax = y > yMax ? y : yMax;
					}
				}
			}

			// ensure capacity in segment_range
			if (xMax > segment_range_capacity)
			{
				int new_capacity = xMax + 10;
				int[][] new_segment_range = new int[new_capacity][];
				for (i = 0; i < new_capacity; ++i)
				{
					if (i < segment_range_capacity)
					{
						new_segment_range[i] = segment_range[i];
					}
					else
					{
						new_segment_range[i] = new int[6] { 0, 6, 0, 0, 0, 0 };
					}
				}
				this.segment_range = new_segment_range;
				this.segment_range_capacity = new_capacity;
			}

			Point point_a, point_b;
			int start, end, t;
			int real_capacity, virtual_length, crossovers;
			int[] segment_list;
			int[] new_segment_list;
			int list_end;

			start = xMin < 0 ? 0 : xMin;

			// reset segment_ranges from previous usage
			for (x = start; x <= xMax; ++x)
			{
				segment_range[x][0] = 0;
			}

			int innerListLength;
			int left_x, right_x, left_y, right_y, span;
			// Populate the segment_range
			for (i = 0; i < points.Length; ++i)
			{
				pointList = points[i];
				innerListLength = pointList.Length;
				for (j = 0; j < innerListLength; ++j)
				{
					point_a = pointList[j];
					point_b = pointList[(j + 1) % innerListLength];
					start = point_a.X;
					end = point_b.X;

					if (start == end)
					{
						// vertical line segments will not be hit by crosslines
						continue;
					}
					else if (start < end)
					{
						left_x = start;
						right_x = end;
						left_y = point_a.Y;
						right_y = point_b.Y;
					}
					else
					{
						left_x = end;
						right_x = start;
						left_y = point_b.Y;
						right_y = point_a.Y;
					}

					span = right_x - left_x;

					for (x = left_x < 0 ? 0 : left_x; x < right_x; ++x)
					{
						segment_list = segment_range[x];
						real_capacity = segment_list[1];
						virtual_length = ++segment_list[0]; // go ahead and add 1

						// do we need to increase capacity?
						if (virtual_length == real_capacity - 1)
						{
							new_segment_list = new int[(real_capacity + 1) * 2];
							segment_list.CopyTo(new_segment_list, 0);
							segment_list = new_segment_list;
							segment_range[x] = segment_list;
							real_capacity = segment_list.Length;
							segment_list[1] = real_capacity;
						}

						t = x - left_x;

						segment_list[virtual_length + 1] = (t * right_y + (span - t) * left_y + (span >> 1)) / span;
					}
				}
			}

			// sort the crossover points into ascending order
			for (x = xMin < 0 ? 0 : xMin; x <= xMax; ++x)
			{
				segment_list = segment_range[x];
				virtual_length = segment_list[0];
				crossovers = virtual_length + 2;
				
				if ((virtual_length & 1) == 1)
				{
					// huh? how do you get an odd number of crossovers?
					// I don't know what happened, but let's amputate the last one for lack of a better idea
					virtual_length--;
					segment_list[0]--;
				}

				if (virtual_length < 2)
				{
					// Nothing to sort. 
				}
				else if (virtual_length == 2)
				{
					// I'm going to go ahead and hardcode sorting for 2 elements. No need to bust out the 
					// complex sorting algorithm when there's only 1 obvious potential swap.
					if (segment_list[2] > segment_list[3])
					{
						t = segment_list[2];
						segment_list[2] = segment_list[3];
						segment_list[3] = t;
					}

					if (yMin > segment_list[2])
					{
						yMin = segment_list[2];
					}

					if (yMax < segment_list[3])
					{
						yMax = segment_list[3];
					}
				}
				else
				{
					// Yes. It's f*#%ing bubble sort. But hey, when you have a concave polygon
					// with a bazillion crossovers you're asking for trouble anyway. I mean, really. 
					// What the hell are you drawing anyway? A procedurally generated ball of twine?
					list_end = virtual_length + 2;
					for (i = 3; i < list_end; ++i)
					{
						for (j = 3; j < list_end - i + 3; ++j)
						{
							if (segment_list[j] < segment_list[j - 1])
							{
								t = segment_list[j];
								segment_list[j] = segment_list[j - 1];
								segment_list[j - 1] = t;
							}
						}
					}

					if (yMin > segment_list[2])
					{
						yMin = segment_list[2];
					}

					if (yMax < segment_list[virtual_length - 1])
					{
						yMax = segment_list[virtual_length - 1];
					}
				}
			}

			// Draw that sucker
			int capacity, y_a, y_b;

			int length;

			for (x = xMin < 0 ? 0 : xMin; x <= xMax; ++x)
			{
				segment_list = segment_range[x];
				length = segment_list[0];

				if (length > 0)
				{
					capacity = length + 2;
					column_affected[x] = counter;
					y_min_affected[x] = segment_list[2];
					y_max_affected[x] = segment_list[length + 1];
					for (i = 2; i < capacity; i += 2)
					{
						y_a = segment_list[i];
						y_b = segment_list[i + 1];
						for (y = y_a; y <= y_b; ++y)
						{
							pixels[x, y] = counter;
						}
					}
				}
			}
		}
	}
}
